/**
 * Version 2.
 * Stream   = List<A>
 * Reason   = None
 * Result   = Pair<B, List<A>>?
 */

/*
package parcomb
import java.util.ArrayList

// basic parsers

fun single<A, B>(result: B, str: List<A>) = Pair<B, List<A>>(result, str)

fun empty() = null

fun result<A, B>(r: B): (List<A>) -> Pair<B, List<A>>? = {(s: List<A>) -> single<A, B>(r, s) }
fun zero<A>() = {(s: List<A>) -> empty() }
fun item<A>() = {(s: List<A>) -> if (s.isEmpty()) null else single<A, A>(s[0], s.subList(1, s.size)) }
fun itemnc<A>() = {(s: List<A>) -> if (s.isEmpty()) null else single<A, A>(s[0], s) }

// main combinators

fun bind<A, B, C>(p: (List<A>) -> Pair<B, List<A>>?,
                  f: (B) -> ((List<A>) -> Pair<C, List<A>>?)): (List<A>) -> Pair<C, List<A>>? = {(s: List<A>) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        f(ans.first)(ans.second)
}

fun seq<A, B, C>(p: (List<A>) -> Pair<B, List<A>>?,
                 q: (List<A>) -> Pair<C, List<A>>?): (List<A>) -> Pair<Pair<B, C>, List<A>>? = bind<A, B, Pair<B, C>>(
        p,
        {(x: B) ->
            bind<A, C, Pair<B, C>>(
                    q,
                    {(y: C) ->
                        result<A, Pair<B, C>>(Pair<B, C>(x, y))
                    }
            )
        }
)

fun sat<A>(f: (A) -> Boolean): (List<A>) -> Pair<A, List<A>>? =
        bind<A, A, A>(item(), {(x: A) -> if (f(x)) result<A, A>(x) else zero() })

fun char<A>(c: A) = sat<A>() { it == c }
fun digit() = sat<Char>() { it in '0'..'9' }
fun lower() = sat<Char>() { it in 'a'..'z' }
fun upper() = sat<Char>() { it in 'A'..'Z' }

fun alt<A, B>(p: (List<A>) -> Pair<B, List<A>>?,
              q: (List<A>) -> Pair<B, List<A>>?) = {(s: List<A>) ->
    val t = p(s)
    if (t != null)
        t
    else
        q(s)
}

fun apply<A, B, C>(p: (List<A>) -> Pair<B, List<A>>?,
                   f: (B) -> C): (List<A>) -> Pair<C, List<A>>? = {(s: List<A>) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        Pair<C, List<A>>(f(ans.first), ans.second)
}

fun letter() = alt(lower(), upper())
fun alphanum() = alt(letter(), digit())

fun nc<A, B>(p: (List<A>) -> Pair<B, List<A>>?) = {(s: List<A>) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        Pair<B, List<A>>(ans.first, s)
}

fun word(): (List<Char>) -> Pair<List<Char>, List<Char>>? = alt(
        bind<Char, Char, List<Char>>(
                letter(),
                {(x: Char) ->
                    bind<Char, List<Char>, List<Char>>(
                            word(),
                            {(xs: List<Char>) -> result<Char, List<Char>>(x cons xs) }
                    )
                }
        ),
        result<Char, List<Char>>(ArrayList<Char>())
)

fun string<A>(str: List<A>): (List<A>) -> Pair<List<A>, List<A>>? =
        if (str.isEmpty())
            result<A, List<A>>(ArrayList<A>())
        else
            bind<A, A, List<A>>(
                    char(str[0]),
                    {(s0: A) ->
                        bind<A, List<A>, List<A>>(
                                string(str.subList(1, str.size())),
                                {(s1: List<A>) ->
                                    result<A, List<A>>(str)
                                }
                        )
                    }
            )

fun many<A, B>(p: (List<A>) -> Pair<B, List<A>>?): (List<A>) -> Pair<List<B>, List<A>>? = alt(
        bind<A, B, List<B>>(
                p,
                {(x: B) ->
                    bind<A, List<B>, List<B>>(
                            many<A, B>(p),
                            {(xs: List<B>) ->
                                result<A, List<B>>(x cons xs)
                            }
                    )
                }
        ),
        result<A, List<B>>(ArrayList<B>())
)

fun many1<A, B>(p: (List<A>) -> Pair<B, List<A>>?): (List<A>) -> Pair<List<B>, List<A>>? =
        bind<A, B, List<B>>(
                p,
                {(x: B) ->
                    bind<A, List<B>, List<B>>(
                            many<A, B>(p),
                            {(xs: List<B>) ->
                                result<A, List<B>>(x cons xs)
                            }
                    )
                }
        )


fun digitToInt(): (List<Char>) -> Pair<Int, List<Char>>? =
        bind<Char, Char, Int>(
                digit(),
                {(x: Char) ->
                    result<Char, Int>(x.toInt() - '0'.toInt())
                }
        )

fun nat(): (List<Char>) -> Pair<Int, List<Char>>? = {(s: List<Char>) ->
    val ans = many1(digitToInt())(s)
    if (ans == null)
        null
    else
        Pair<Int, List<Char>>(ans.first.foldl({(x: Int, y: Int) -> x * 10 + y }, 0), ans.second)
}

fun int(): (List<Char>) -> Pair<Int, List<Char>>? = alt(
        bind<Char, Char, Int>(
                char('-'),
                {(x: Char) ->
                    bind<Char, Int, Int>(
                            nat(),
                            {(n: Int) -> result<Char, Int>(-n) }
                    )
                }
        ),
        nat()
)

fun chainl1<A, B>(p: (List<A>) -> Pair<B, List<A>>?,
                  op: (List<A>) -> Pair<(B, B) -> B, List<A>>?): (List<A>) -> Pair<B, List<A>>? = {(s: List<A>) ->
    val op2f = seq(op, p)
    val fys = many(op2f)
    bind<A, B, B>(
            p,
            {(x: B) ->
                bind<A, List<Pair<(B, B) -> B, B>>, B>(
                        fys,
                        {(xs: List<Pair<(B, B) -> B, B>>) ->
                            result(xs.foldl(
                                    {(x1: B, x2: Pair<(B, B) -> B, B>) -> x2.first(x1, x2.second) },
                                    x
                            ))
                        }
                )
            }
    )(s)
}

// expression parser

fun bracket<A, B, C, D>(
        open: (List<A>) -> Pair<B, List<A>>?,
        p: (List<A>) -> Pair<C, List<A>>?,
        close: (List<A>) -> Pair<D, List<A>>?): (List<A>) -> Pair<C, List<A>>? =
        bind<A, B, C>(
                open,
                { bind<A, C, C>(p, {(ans: C) -> bind<A, D, C>(close, { result<A, C>(ans) }) }) }
        )

fun getOp(op: Char) =
        when (op) {
            '+' -> {(x: Int, y: Int) -> x + y }
            '-' -> {(x: Int, y: Int) -> x - y }
            '*' -> {(x: Int, y: Int) -> x * y }
            else -> {(x: Int, y: Int) -> 0 }
        }

fun addop(): (List<Char>) -> Pair<((Int, Int) -> Int), List<Char>>? = alt(
        apply(char<Char>('+'), {(c: Char) -> getOp(c) }),
        apply(char<Char>('-'), {(c: Char) -> getOp(c) })
)

fun expr() = chainl1<Char, Int>(factor(), addop())

fun factor(): (List<Char>) -> Pair<Int, List<Char>>? = alt(
        digitToInt(),
        bracket(char('('), {(s: List<Char>) -> expr()(s) }, char(')'))
)

*/